1. Field of the Invention
The present invention generally provides a method and system for placing logic nodes based on an estimated wiring congestion. Specifically, the present invention provides a method and system for placing logic nodes into bins of a chip based on a comparison of an estimated wiring congestion to a wiring availability.
2. Background Art
In the manufacture of microelectronics, circuits and other logic must be placed on chips under certain wireability and timing constraints. Specifically, the nodes must be placed so that the wiring interconnects between the nodes are within the wiring constraints of the chip. Moreover, the wiring interconnects between the logic nodes cannot be placed arbitrarily close to each other. Rather, a certain wiring pitch must be observed. Placement of nodes on a chip is especially problematic when the wiring requirements between the logic nodes approaches the wiring availability. In these situations, the resulting wiring congestion can cause “hot spots” on the chip, which can lead to overload and failure thereof.
Therefore, it is necessary to optimize the placement of logic nodes on the chip so that overload does not occur, while still allowing all required wiring interconnects to be made. Heretofore, attempts have been made to provide improved circuit placement. In general, such attempts begin by positioning the logic nodes on a chip. The chip is then divided/partitioned into a first placement level having four bins or quadrants. The logic nodes are then arranged in the four bins. Next, each of the four bins are partitioned into a second placement level having four sub-bins, and the logic nodes for each bin are arranged in the corresponding sub-bins. The process can then be repeated for subsequent placement levels until a minimum bin size is reached. Although this allows the logic nodes to be physically positioned on the chip, it does not guarantee a wireable chip placement. To provide a wireable chip placement, a user must subsequently either: (1) manually identify the positioned logic nodes that cause wiring congestion and reduce the circuit density accordingly; or (2) reduce the overall chip density by increasing the chip size. In the case of the former, several time-consuming iterations are required. In the case of the latter, increasing the chip size will led to a substantial increase in cost.
In view of the foregoing, there exists a need for a method and system for placing logic nodes based on an estimated wiring congestion. A need also exists for a method and system for placing logic nodes based on relative probabilities that potential implementations of wiring interconnects between logic nodes will cross over an edge of a bin. A further need exists for a method and system for placing logic nodes based on a comparison of an estimated wiring congestion to a wiring availability.